
/**
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findMedianSortedArrays(new int[]{2}, new int[]{})); //2
        System.out.println(solution.findMedianSortedArrays(new int[]{1, 3}, new int[]{2})); //2
        System.out.println(solution.findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4})); //2.5
        System.out.println(solution.findMedianSortedArrays(new int[]{1}, new int[]{2, 3, 4})); //2.5
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length == 0) {
            boolean isOdd = (nums2.length & 1) == 1;
            return single(isOdd, nums2, 0, isOdd ? nums2.length / 2 : (nums2.length / 2) - 1);
        } else if (nums2.length == 0) {
            boolean isOdd = (nums1.length & 1) == 1;
            return single(isOdd, nums1, 0, isOdd ? nums1.length / 2 : (nums1.length / 2) - 1);
        }

        int total = nums1.length + nums2.length;

        int mid = total / 2;
        int left = 0;
        int right = 0;
        if ((total & 1) == 1) {
            //奇数
            while (mid > 0) {
                if (nums1[left] >= nums2[right]) {
                    right++;
                } else {
                    left++;
                }
                mid--;

                if (left == nums1.length) {
                    return single(true, nums2, right, mid);
                }
                if (right == nums2.length) {
                    return single(true, nums1, left, mid);
                }
            }

            if (nums1[left] >= nums2[right]) {
                return nums2[right];
            } else {
                return nums1[left];
            }

        } else {
            //偶数
            mid--;
            while (mid > 0) {
                if (nums1[left] >= nums2[right]) {
                    right++;
                } else {
                    left++;
                }
                mid--;

                if (left == nums1.length) {
                    return single(false, nums2, right, mid);
                }
                if (right == nums2.length) {
                    return single(false, nums1, left, mid);
                }
            }

            int first, second;
            if (nums1[left] >= nums2[right]) {
                first = nums2[right];
                right++;
            } else {
                first = nums1[left];
                left++;
            }

            if (left == nums1.length) {
                second = nums2[right];
                return (double) (first + second) / 2;
            }
            if (right == nums2.length) {
                second = nums1[left];
                return (double) (first + second) / 2;
            }

            if (nums1[left] >= nums2[right]) {
                second = nums2[right];
            } else {
                second = nums1[left];
            }

            return (double) (first + second) / 2d;
        }

    }

    private double single(boolean isOdd, int[] arr, int index, int count) {
        if (arr.length == 0) {
            return 0;
        }
        while (count > 0) {
            index++;
            count--;
        }
        if (isOdd) {
            return arr[index];
        } else {
            return (double) (arr[index] + arr[index + 1]) / 2;
        }
    }

}